package anthology.daily_question._24_11;
//https://leetcode.cn/problems/count-substrings-that-satisfy-k-constraint-i/description/?envType=daily-question&envId=2024-11-12
public class _3258统计满足K约束的子字符串数量1 {
    public static int countKConstraintSubstrings2(String s, int k) {
        int n = s.length(), res = 0;
        for (int i = 0; i < n; ++i) {
            int[] count = new int[2];
            for (int j = i; j < n; ++j) {
                count[s.charAt(j) - '0']++;
                if (count[0] > k && count[1] > k) {
                    break;
                }
                res++;
            }
        }
        return res;
    }

    //枚举
    public static int countKConstraintSubstrings(String s, int k) {
        char[] dp = s.toCharArray();
        int len = dp.length,count = 0;
        for(int i=0; i<len; i++){
            int k0 = 0,k1 = 0;
            for(int j=i; j<len; j++){
                if(dp[j]=='0'){
                    k0++;
                }else{
                    k1++;
                }
                if(k0 > k && k1 > k)
                    break;
                count++;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(countKConstraintSubstrings("110010001", 2));
        System.out.println(countKConstraintSubstrings("10101", 1));
        System.out.println(countKConstraintSubstrings2("10101", 1));
    }
}
